#include "MyDynamicArray.h"
#include <stdio.h>
#include <stdlib.h>


bool MyInsertArrayTail(DArray *a,ElementType element);
bool MyRemoveByElement(DArray *a,ElementType element,bool (*funcPtr)(ElementType,ElementType),void (*ClearPtr)(ElementType));
DArray MyFindElement(DArray *a,ElementType element,bool (*funcPtr)(ElementType,ElementType));
void MyDisplayDynamicArray(DArray *a,void (*funcPtr)(ElementType));
void MySort(DArray *a,bool (*funcPtr)(ElementType,ElementType));
void MyClearDynamicArray(DArray *a,void (*funcPtr)(ElementType));


void MyInitDynamicArray(DArray *a)
{
    a->dp = NULL;
    a->len = 0;
    a->size = 0;

    a->MyInsertArrayTail = MyInsertArrayTail;
    a->MyRemoveByElement = MyRemoveByElement;
    a->MyFindElement = MyFindElement;
    a->MyDisplayDynamicArray = MyDisplayDynamicArray;
    a->MySort = MySort;
    a->MyClearDynamicArray = MyClearDynamicArray;
}

bool MyInsertArrayTail(DArray *a,ElementType element)
{
    if(a->dp == NULL)
    {
        a->size = (a->size + 1) * 2;
        a->dp = (ElementType)malloc(sizeof(ElementType) * a->size);
        if(a->dp == NULL)
        {
            MyInitDynamicArray(a);
            return false;
        }
    }
    else if(a->size <= a->len)
    {
        int newSize = (a->size + 1) * 2;
        ElementType *newDp = (ElementType)realloc(a->dp,newSize * sizeof(ElementType));
        if(newDp == NULL)
        {
            return false;
        }
        a->size = newSize;
        a->dp = newDp;
    }
    a->dp[a->len++] = element;
    return true;
}

bool RemoveByIndex(DArray *a,int index,void(*ClearPtr)(ElementType))
{
    if(index < 0 || index >= a->len)
    {
        printf("删除的非法位置!\n");
        return false;
    }
    if(ClearPtr != NULL)
    {
        ClearPtr(a->dp[index]);
    }
    for(int i = index; i < a->len - 1; i ++)
    {
        a->dp[i] = a->dp[i+1];
    }
    a->len--;
    return true;
}

bool MyRemoveByElement(DArray *a, ElementType element, bool (*funcPtr)(ElementType, ElementType), void (*ClearPtr)(ElementType))
{
    for(int i = 0; i < a->len; i++)
    {
        if(funcPtr(element,a->dp[i]) == true)
        {
            if(RemoveByIndex(a,i,ClearPtr) == false)
            {
                return false;       
            }
            i--;
        }
    }
    return true;
}

DArray MyFindElement(DArray *a, ElementType element, bool (*funcPtr)(ElementType, ElementType))
{
    DArray result;
    MyInitDynamicArray(&result);
    for(int i = 0; i < a->len; i++)
    {
        if(funcPtr(element,a->dp[i]) == true)
        {
            MyInsertArrayTail(&result,a->dp[i]);
        }
    }
    return result;
}

void MyDisplayDynamicArray(DArray *a, void (*funcPtr)(ElementType))
{
    for(int i = 0; i < a->len; i++)
    {
        funcPtr(a->dp[i]);
    }
}

void FastSort(ElementType *s,int start,int end, bool(*funcptr)(ElementType, ElementType))
{
    if(start >= end)
    return;
    ElementType temp = s[start];
    int left = start;
    int right = end;
    
    while(left < right)
    {
        while(left < right && funcptr(s[right],temp) == true)
        {
            right--;
        }
        if(left < right)
        {
            s[left] = s[right];
            left++;
        }
        while(left < right && funcptr(s[left],temp) == false)
        {
            left++;
        }
        if(left < right)
        {
            s[right] = s[left];
            right--;
        }
        s[left] = temp;
    }
    FastSort(s,start,left - 1,funcptr);
    FastSort(s,right + 1,end,funcptr);
}

void MySort(DArray *a, bool (*funcPtr)(ElementType, ElementType))
{
    FastSort(a->dp,0,a->len-1,funcPtr);
}

void MyClearDynamicArray(DArray *a, void (*funcPtr)(ElementType))
{
    if(funcPtr != NULL)
    {
        for(int i = 0; i < a->len; i++)
        {
            funcPtr(a->dp[i]);
        }
    }
    free(a->dp);
    MyInitDynamicArray(a);
}
